package leetcodecompetition.S115;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-10-14-23:02
 * @Description: 1.0
 */
public class T100077 {
    String[] words;
    int[] groups;

    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
        this.words = words;
        this.groups = groups;
        int[][] preLen = new int[n][2];
        preLen[0] = new int[]{-1, 1};
        int m = 0, mI = -1;
        for (int i = 0; i < n; i++) {
            int max = 0, maxIndex = -1;
            for (int j = 0; j < i; j++) {
                if (f(i, j) && preLen[j][1] > max) {
                    max = preLen[j][1];
                    maxIndex = j;
                }
            }
            preLen[i] = new int[]{maxIndex, max + 1};
            if (max + 1 > m) {
                m = max + 1;
                mI = i;
            }
        }

        List<String> res = new ArrayList<>();
        int[] resArr = new int[m];
        int p = mI;
        for (int i = m - 1; i >= 0; i--) {
            resArr[i] = p;
            p = preLen[p][0];
        }
        for (int i = 0; i < m; i++) {
            res.add(words[resArr[i]]);
        }
        return res;


    }

    public boolean f(int a, int b) {
        if (groups[a] == groups[b] || words[a].length() != words[b].length()) return false;
        int n = words[a].length(), dif = 0;
        for (int i = 0; i < n; i++) {
            if (words[a].charAt(i) != words[b].charAt(i)) dif++;
        }
        return dif == 1;
    }
}
